package 双指针.二分查找;

/**
 * 解题思路：
 *  X 平方根的整数部分 k  一定满足 k²<=x.
 *  所以我们只要用二分法不断缩小范围找到满足该条件的最大值k
 *
 *  下界为0，上界最开始设置为x。我们就只需要在每次二分范围内比较mid²与x的关系，如果大了就缩小上界right
 *  小了或等于了就增大下界left
 */
public class x的平方根_69 {

    public static void main(String[] args) {
      System.out.println(new x的平方根_69().mySqrt(6))  ;

    }

    public int mySqrt(int x) {
        int l = 0, r = x, ans = -1;
        while (l <= r) {//之所以要循环到l>r是为了保证找到的是最大值
            int mid = l + (r - l) / 2;//其实mid就等于(l+r)/2，这里这么写是为了防止溢出
            if ((long) mid * mid <= x) {//用long 也是为了防止mid过大而导致溢出。
                ans = mid;//因为k满足k²<=x，所以结果只会出现在mid²<=x的情况下
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }


}
